The invention relates to an apparatus and a method for locating a Global Navigation Satellite System (GNSS) receiver when estimates of its position and absolute time are unknown.
Satellite Location-Systems
The Global Positioning System (GPS) is an example of a GNSS navigation system in which a receiver determines its position by precisely measuring the arrival time of signalling events received from multiple satellites. Each satellite transmits a navigation message containing the precise time when the message was transmitted and ephemeris information. Each sub-frame of the navigation message starts with a telemetry word (TLM) which contains a preamble (10001011), a Telemetry Message and an Integrity Status Flag. The start of the sub-frame may be detected by means of a preamble sequence in the TLM. Each sub-frame also includes a handover word (HOW) and the sub-frame ID. The first 17 bits of the HOW give a truncated version of the exact time of the week (TOW) at which the satellite will transmit the next sub-frame according to the local version of GPS time held by the satellite's clock. The ephemeris information includes details about the satellite's orbit and corrections for the satellite's own clock, in comparison with GPS time. The ephemeris and clock correction parameters may be known collectively as ephemeris information. Alternative formats for the navigation data are used for GPS as defined (for example) in the CNAV message; and in other GNSS broadcasts, as defined in the appropriate signal-in-space interface control documentation.
GPS signals are formed of a navigation message binary phase shift modulated (BPSK) onto a direct sequence spread spectrum signal. The spread spectrum signal comprises a unique pseudo-noise (PN) code that identifies the satellite. For civil applications, GPS signals are transmitted using the L1, L2 and L5 frequencies. On the L1 frequency, the civil signal (dual use transmission) uses a spreading code known as the C/A code (coarse/acquisition). The C/A code has a sequence length of 1023 chips and changes to the next designated state at a 1.023 MHz chipping rate. The code sequence repeats every millisecond. The code sequence has an identified start instant when the two code generators in the satellite (as shown in IS GPS 200) transition to the all ‘1's’ state. This instant is known as the code epoch. Some satellites may use an alternative, but equivalent, code sequence mechanisation.
After various transport delays in the satellite, the code epoch is broadcast through the timing and sequencing of specific code states assigned to the satellite. This signalling event can be recognised, in suitably adapted receivers, through a process of aligning a replica code with the code received from each satellite.
The L1 C/A code navigation message has a data rate of 50 bits per second, lower than the code rate, and its data bit or symbol transitions are synchronised with the start of the C/A code sequence. Each bit of the navigation message lasts for 20 milliseconds and thus incorporates 20 repetitions of the C/A code. The navigation message is constructed from a 1500-bit frame consisting of five 300-bit sub-frames. Each sub-frame lasts for 6 seconds. The satellite transmits the navigation message and C/A code using a carrier frequency that is an integer multiple of 10.23 MHz (for the L1 carrier, the multiple is 154). At the start of a GPS week, a satellite will transmit the first code cycle, of the first data bit, of the first sub-frame of the first frame of the navigation data.
In addition to the time and ephemeris information, the navigation message also contains the satellite constellation almanac, parameters representing a model of the ionospheric and tropospheric delay, health parameters and other information used by some receivers. There are 25 different frames of data broadcast from each satellite. Each frame contains identical information (apart from time) in sub-frames 1-3 inclusive but cycles through a pre-assigned sequence of data in sub-frames 4 and 5, which contain almanac and other information. The ephemeris information, including the satellite clock biases, is periodically refreshed by the GPS Control Segment, typically every 2 hours, so that the navigation data message is representative of the current orbit model and status of each satellite. There are indicators in the navigation message which provide the user with knowledge of when the ephemeris and clock data has been changed. Details of these changes are set out in the GPS interface standard, IS GPS 200.
As mentioned above, a GPS receiver may determine the time-of-arrival of a signalling event through a process of aligning a replica code with the code received from each satellite. The receiver may also use the TOW information contained in the navigation message to determine the time when the signalling event was transmitted. From this, the receiver can determine the transit time for the signalling event (from which it can determine the distance between it and the satellite), together with the position of the satellite at the time when the signalling event was transmitted (using the ephemeris information). The receiver can then calculate its own position. Theoretically, the position of the GPS receiver can be determined using signals from three satellites, providing the receiver has precise knowledge of absolute time or knowledge of part of the positions, such as altitude. However, in practice GPS receivers use signals from four or more satellites to determine an accurate three-dimensional location solution because an offset between the receiver clock and GPS time introduces an additional unknown into the calculation.
If the satellite signal reception is poor (commonly known as weak signal conditions), or if the receiver only receives a short burst of the signal, the receiver may not be able to decode the TOW information. Without this information, the GPS receiver may be unable to determine the distance between it and the satellite with sufficient accuracy because the receiver will not know the time when the signalling event was transmitted. Under weak signal conditions or briefly glimpsed signals, the receiver may also be unable to recognise the start of a sub-frame since it may not be able to decode the preamble sequence in the TLM.
A receiver that has been unable to decode the TLM and TOW information in the navigation message may nonetheless be able to deduce some timing information even under weak signal conditions or from briefly-glimpsed signals. For example, the receiver may be able to determine a time shift between the satellite signal's spreading (PN) code and a locally generated version of the same, e.g. by correlating the received signal with a locally generated replica of the PN code or by using an equivalent signal processing technique. This time shift represents at least part of the transit time for the satellite signal. However, since both the PN code in the signal and the locally generated replica code are of finite length in space (known as the code wavelength), the correlation operation can only identify a part of the total time shift. This part of the total time shift represents a fractional part of the signal transit time between satellite and the receiver. The integer number of code repetition intervals the signal took to travel between the satellite and the receiver cannot be measured by the receiver, nor can the integer number of code repetition intervals from the start of week in order to establish the absolute time of transmission.
In order to compute its position accurately, the receiver also needs to be able to resolve discrepancies between the various clocks in the system. GPS time is defined by an ensemble of clocks generally located at the US Naval Observatory in Washington. Each satellite has its own operating clock (usually one of three on board the space vehicle), which is approximately synchronised with GPS time. In practice, however, the satellite clock is offset from GPS time by a small amount. The receiver clock is also likely to be offset from GPS time, at least prior to an initial location solution. Uncorrected, these clock biases introduce significant errors into the location calculation.
“GPS Receiver Structures for the Urban Canyon” by Peterson et al. presents a method for computing the position of a GPS receiver in a deep urban canyon, in which the receiver may obtain brief glimpses of satellites but rarely sees three or more satellites simultaneously. The method addresses the problem of having an unknown common system time by expanding the location calculation to encompass an additional satellite range measurement and an additional unknown parameter termed “coarse time”. The Peterson paper thus proposes a solution in which signals from five satellites are required for a 3D-location solution.
“Fast Acquisition Techniques for GPS Receivers” by Lannelongue et al. also presents a method for computing the position of a GPS receiver in which the common system time is unknown.
The integer millisecond ambiguity is also addressed by U.S. Pat. No. 6,417,801, which describes a way of estimating the integer milliseconds by calculating the geometric pseudo-range of the receiver to the satellite. The geometric pseudo-range is calculated using an estimated position of the GPS receiver and the position of the satellite at an estimated GPS time. U.S. Pat. No. 6,417,801 estimates the number of integer milliseconds that the signal took to travel between the satellite and the GPS receiver from the estimated pseudo-range and adds this to a measured, sub-millisecond pseudo-range to obtain a ‘full’ pseudo-range. The full pseudo-ranges from five satellites are then used to calculate the location of the GPS receiver. This technique is also described in “A-GPS: Assisted GPS, GNSS and SBAS 72” by Frank Van Diggelen (see chapter 4).
Mathematical techniques may be used to change the unknowns output by the location calculation. For example, U.S. Pat. No. 7,064,709 explains that calculating the integer number of milliseconds using estimated pseudo-ranges is not always sufficiently accurate and instead proposes a method whereby a common transit delay, represented as an number of integer milliseconds, is inserted as one of the unknowns to be determined as part of the location calculation. U.S. Pat. No. 7,064,709 also proposes that differences may be used to create four equations and four unknowns from the five equations using satellite measurements.
U.S. Pat. No. 6,191,731 also describes making five range measurements to five satellites and solving the five resulting equations by weighting and subtracting one from the four others in order to eliminate one of the unknown terms. This is a purely mathematical procedure which, in this example, cancels the user clock error term from the five linearised position equations.
These techniques are similar to the differencing methods used in some land survey implementations in which GPS time is known. Signals from two different satellites are differenced at one receiver and that difference is then subtracted from a similar difference calculated at another receiver. This double-difference technique allows unknowns such as the satellite and receiver clock errors to be eliminated from the calculation. These techniques are generally operative only within a zone where the location solution converges with a low error.
Another method is the so-called ‘Single-Difference’ method in which one of the satellites is designated as a reference satellite. The estimated distances and transit times from four satellites are compared with the equivalent values for a reference satellite. This has two advantages: first, it addresses the issue of integer ambiguity in the measured times-of-arrival; and second, it removes the receiver clock bias as an unknown at the instant of measurement, as the arrival of each signalling event is measured with reference to the arrival of the signalling event from the reference satellite. In this way, the receiver clock bias does not contaminate the measurements and does not enter into the location calculations. The receiver clock is used, however, to provide a timescale for measuring the time differences between the arrival times of the various signalling events. This method is described in more detail below.
The “Single-Difference” Approach
FIG. 1 shows a GPS receiver 101 receiving GPS signals 107a and 107b from two GPS satellites, 103 and 104. Each satellite is travelling according to a respective orbit (105 and 106). The GPS receiver may designate one of these satellites as a reference satellite. This satellite sets the time base against which all other signals are measured.
First consider the case of a signal received from single satellite 104. The time-of-arrival of signalling event 107b at GPS receiver 101 can be expressed as:
                              t                      rx            ,            i                          =                              t                          sat              ,              i                                +                                                    D                i                            ⁡                              (                                  t                                      sat                    ,                    i                                                  )                                      c                    +                                    (                                                B                  U                                -                                  B                                      SV                    ,                    i                                                              )                        c                    +                                    (                                                d                                      iono                    ,                    i                                                  +                                  d                                      tropo                    ,                    i                                                              )                        c                    +                      ɛ            i                                              (        1        )            
where:
trx,i is the arrival time of the signalling event transmitted by satellite i at the receiver (which in this instance is the full time-of-arrival rather than just the fractional part; ambiguity in the measured time-of-arrival and how it may be resolved are discussed later);
tsat,i is the time when the signalling event was transmitted;
Di(tsat,i) is the distance between the receiver and satellite i;
BU is the receiver clock bias, expressed in terms of distance;
BSV,i is the clock bias of satellite i, expressed in terms of distance, and is a function of tsat,i;
diono,i and dtropo,i are the excess delays due to signal transition through the ionosphere and troposphere, over those in free space, expressed in terms of distance;
εi is the measurement error, which is mainly due to noise and multipath errors; and
c is the speed of light in meters per second.
Equation (1) can be extended by comparing signalling event 107b received from satellite 104 with signalling event 107a from reference satellite 103. Rather than consider each time-of-arrival independently, the receiver may measure only the difference between the arrival times. This eliminates the receiver clock bias, which is identical for both. The receiver clock bias is the difference between the time held in the receiver clock to an absolute or reference time, such as GPS time. If it is assumed that the transmitted events occurred at the same GPS time (as measured by each satellite), this gives the following equation:
                                          t                          rx              ,              i                                -                      t                          rx              ,              0                                      =                                                                              D                  i                                ⁡                                  (                  t                  )                                            -                                                D                  0                                ⁡                                  (                  t                  )                                                      c                    +                                    (                                                B                                      SV                    ,                    0                                                  -                                  B                                      SV                    ,                    i                                                              )                        c                    +                                    (                                                d                                      iono                    ,                    i                                                  -                                  d                                      iono                    ,                    0                                                  +                                  d                                      tropo                    ,                    i                                                  -                                  d                                      tropo                    ,                    0                                                              )                        c                    +                      (                                          ɛ                i                            -                              ɛ                0                                      )                                              (        2        )            
Where the reference satellite is designated by the subscript ‘0’ and t designates the absolute time corresponding to the signalling event transmitted by each satellite.
A problem with solving equation (2) is that under weak signal conditions the receiver may be unable to distinguish the arrival of repetitive events from each other. For example, a GPS receiver may be able to detect the start of each code epoch, even under weak signal conditions, but those code epochs repeat at 1 ms intervals. Without being able to decode more of the signal, therefore, the receiver is unable to directly identify which of the repetitive signalling events received from the ith satellite and the reference satellite were transmitted at the same GPS time (as measured by each satellite). It is therefore unclear which times-of-arrival should be compared with each other in calculating trx,i−trx,0.
One option is to predict a likely time-of-arrival for a signalling event transmitted by the ith satellite using the time-of-arrival of the corresponding signalling event from the reference satellite, estimated distances between the receiver and each of the satellites and the differences in the clock biases between the satellites.
The distance between the ith satellite and the receiver may be defined as the Euclidean norm of the difference in vector positions, (xsat,i−x), where xsat,i is the position vector of the ith satellite and x is the position vector of the receiver. The estimated distance between the ith satellite and the receiver may be defined as the Euclidean norm of the difference in vector positions, (xsat,i(te)−xe), where xsat,i(te) is the position vector that corresponds to the location of the ith satellite at an initial estimate of (GPS) time te and xe is the position vector corresponding to an initial estimate of the location of the receiver. This gives rise to the following equations:Di(t)=√{square root over ((xSV,i(t)−x)2+(ySV,i(t)−y)2+(zSV,i(t)−z)2)}{square root over ((xSV,i(t)−x)2+(ySV,i(t)−y)2+(zSV,i(t)−z)2)}{square root over ((xSV,i(t)−x)2+(ySV,i(t)−y)2+(zSV,i(t)−z)2)}{circumflex over (D)}i(te)=√{square root over ((xSV,i(te)−x0)2+(ySV,i(te)−y0)2+(zSV,i(te)−z0)2)}{square root over ((xSV,i(te)−x0)2+(ySV,i(te)−y0)2+(zSV,i(te)−z0)2)}{square root over ((xSV,i(te)−x0)2+(ySV,i(te)−y0)2+(zSV,i(te)−z0)2)}  (3)
Once a time-of-arrival for the signal has been predicted, the actual time-of-arrival of a signalling event from the jth satellite that is closest to that predicted time may be selected as the actual time-of-arrival. Subtracting the predicted time-of-arrival from the actual time-of-arrival gives a single difference residual, which can be converted into an equivalent range residual, through division by the speed of light, c. The single-difference range residual may be defined as follows:∇rrx,i0=∇Rrx,i0−({circumflex over (D)}i(te)−{circumflex over (D)}0(te))+∇Bi0  (4)
where:
∇rrx,i0 is the single difference residual in range, the error arising from errors in the original estimates of GPS time and GPS receiver position;
∇Rrx,i0 is the difference in range between the reference satellite and satellite i as indicated by the times-of-arrival of the signals from those satellites;
{circumflex over (D)}i(te) is the estimated distance between the GPS receiver and the reference satellite at the estimated GPS time, te;
{circumflex over (D)}0(te) is the estimated distance between the GPS receiver and satellite i at the estimated GPS time, te; and
∇Bi0 is the (single) difference in the clock biases of the reference satellite and satellite i expressed in terms of distance.
The expression for {circumflex over (D)}i(te) can be substituted into equation (4) to give an expression for the single difference residual in terms of the initial estimates of receiver position and absolute time. Using a Taylor Series approximation, limited to the first two terms, and combining together the equations for each non-reference/reference satellite combination, equation (4) can be rewritten as:
                                                                                                                                                                                                                                                                                                                                                                ∇                                                                          r                                      10                                                                                                                                                                                                                                                                        ∇                                                                          r                                      20                                                                                                                                                                                                                                                                                                ⋮                                                                                                                                                                          ⋮                                                                                                                                            ∇                                      r                                          n                      ⁢                                                                                          ⁢                      0                                                                                                                    =                                                                                                              -                                          ∇                                              cos                        ⁡                                                  (                                                      α                                                          x                              ⁢                                                                                                                          ⁢                              1                                                        0                                                    )                                                                                                                                                          -                                          ∇                                              cos                        ⁡                                                  (                                                      α                                                          y                              ⁢                                                                                                                          ⁢                              1                                                        0                                                    )                                                                                                                                                          -                                          ∇                                              cos                        ⁡                                                  (                                                      α                                                          z                              ⁢                                                                                                                          ⁢                              1                                                        0                                                    )                                                                                                                                                          (                                                                                            ρ                          .                                                1                                            -                                                                        ρ                          .                                                0                                                              )                                                                                                                    -                                          ∇                                              cos                        ⁡                                                  (                                                      α                                                          x                              ⁢                                                                                                                          ⁢                              2                                                        0                                                    )                                                                                                                                                          -                                          ∇                                              cos                        ⁡                                                  (                                                      α                                                          y                              ⁢                                                                                                                          ⁢                              2                                                        0                                                    )                                                                                                                                                          -                                          ∇                                              cos                        ⁡                                                  (                                                      α                                                          z                              ⁢                                                                                                                          ⁢                              2                                                        0                                                    )                                                                                                                                                          (                                                                                            ρ                          .                                                2                                            -                                                                        ρ                          .                                                0                                                              )                                                                                                ⋮                                                  ⋮                                                                                                                                                                                                                                                                                                                                                      ⋮                                                                                                                                                                                                                                                                                  -                                          ∇                                              cos                        ⁡                                                  (                                                      α                            xn                            0                                                    )                                                                                                                                                          -                                          ∇                                              cos                        ⁡                                                  (                                                      α                            yn                            0                                                    )                                                                                                                                                          -                                          ∇                                              cos                        ⁡                                                  (                                                      α                                                          z                              ⁢                                                                                                                          ⁢                              2                                                        0                                                    )                                                                                                                                                          (                                                                                            ρ                          .                                                n                                            -                                                                        ρ                          .                                                0                                                              )                                                                                            ·                                                                                                                                                                                                                                                                        Δ                                ⁢                                                                                                                                  ⁢                                x                                                                                                                                                                                                        Δ                                ⁢                                                                                                                                  ⁢                                y                                                                                                                                                                                                                                                  Δ                          ⁢                                                                                                          ⁢                          z                                                                                                                                                                                      Δ                    ⁢                                                                                  ⁢                    t                                                                                                                      (        5        )            
Or, more compactly in matrix form, as:∇r=∇H·ΔX 
where
∇ri0 are the single difference residuals for the ith satellite and the reference satellite, expressed in terms of distance;
∇ cos(αxi0), ∇ cos(αyi0) and ∇ cos(αzi0) are the differences in the direction cosines for the ith satellite and the reference satellite;
∇H is defined as the single difference observation matrix, which can be derived from the observation or geometry matrix;
{dot over (ρ)}i is the velocity of the ith satellite resolved along the line-of-sight between the receiver and the ith satellite; and
Δx, Δy, Δz and Δt are the errors in the originally estimated user position and GPS time.
The equation can be exactly solved with a minimum of four single difference measurements (using five satellites). There is a unique solution which provides corrections to (x, t):ΔX=∇H−1·∇r  (6)
The algorithm above was described on the basis that all signalling events were transmitted at the same absolute time (according to the satellites' clocks). A similar algorithm selects signalling events that were transmitted at different absolute times according to the satellites' clocks. The algorithm is essentially the same as that described above, except that the predicted time-of-arrival for the ith satellite additionally incorporates compensation for the difference in transmission times between the signalling events transmitted by the reference satellite and the ith satellite.
An example of how the single-difference method described above might be implemented in practice is described below. In this example, the location system is a GPS system and the receiver is only capable of decoding the C/A code in the received satellite signals. The signalling events detected by the receiver are code epochs, the time between repetitive signalling events is 1 ms and the receiver is able to determine times-of-arrival of the signalling events that are sub-one-millisecond. This is for the purposes of example only, as the algorithm described below is equally applicable to other satellite navigation systems, to definitions of signalling events other than code epochs, and to scenarios in which the receiver is able to measure a greater or lesser portion of the transit time of the signalling event.
This example of the single-difference algorithm may be explained by first splitting the full time-of-arrival of equation (1) into its integer and fractional components on the left hand side, and using tgps as the time of that the signalling event was transmitted from the satellite:
                                          τ            i                    +                      N            i                          =                              t            gps                    +                                                    D                i                            ⁡                              (                                  t                  gps                                )                                      c                    +                                    (                                                B                  U                                -                                  B                                      SV                    ,                    i                                                              )                        c                    +                                    (                                                d                                      iono                    ,                    i                                                  +                                  d                                      tropo                    ,                    i                                                              )                        c                    +                      ɛ            i                                              (        7        )            
τi is the fractional, measured part of the time-of-arrival (sub-one-millisecond) and Ni is the unobserved integer part of the time-of-arrival (an unknown integer number of milliseconds, more generally representing an unknown integer number of code repetition intervals from start of week).
Once again, the reference satellite can be used to set a reference time against which all other satellites are compared. Taking the difference between equation 7 and a reference satellite yields the following equation, noting that the tilde over the τ terms signifies that these signalling event arrival times are corrected for the satellite clock bias:
                                                        τ              ~                        i                    =                                    τ              i                        +                                          B                                  SV                  ,                  i                                            c                                      ⁢                                  ⁢                                            (                                                                    τ                    ~                                    i                                -                                                                                                    D                        ^                                            i                                        ⁡                                          (                                              x                        ,                        t                                            )                                                        /                  c                                            )                        -                          (                                                                    τ                    ~                                    0                                -                                                                                                    D                        ^                                            0                                        ⁡                                          (                                              x                        ,                        t                                            )                                                        /                  c                                            )                                =                                    -                              (                                                      N                    i                                    -                                      N                    0                                                  )                                      +                          (                                                                    ɛ                    ~                                    i                                -                                                      ɛ                    ~                                    0                                            )                                                          (        8        )            
The residual ionospheric and tropospheric errors have been subsumed into the error terms, {tilde over (ε)}, in equation 8. If estimates of the ionospheric and tropospheric excess delays are available, the signal transit times can be adjusted for this prior knowledge, thereby reducing the error term. All of the terms on the left-hand side of equation (8) are known or can be estimated. The right-hand side of equation (8) is close to an integer millisecond since the errors are small. A modulo operation can be performed on both sides of equation (8) to remove the integer millisecond component as an unknown:|({tilde over (τ)}i−{circumflex over (D)}i(t)/c)−({tilde over (τ)}0−{circumflex over (D)}0(t)/c)|mod 1ms=({tilde over (ε)}i−{tilde over (ε)}0)  (9)
Equations 7 through 9 inclusive can be converted from time to distance through multiplication throughout by the speed of light, c. The term c·τi represents the sub-code wavelength part of the distance between the receiver and the ith satellite.
When equation (9) is evaluated with estimated distances, rather than the true distances, correct elimination of the integer term is achieved when (excepting a small region of error due to the effects of noise and multipath represented by c. (εi−ε0)):|(Di−{circumflex over (D)}i(xe,te))−(D0−{circumflex over (D)}0(xe,te))|<0.5λc  (10)
Equation 10 represents a re-organisation of equations 7 and 8 through the replacement of the signalling event transit time by the satellite to receiver distance, Di, D0. In addition, xe and te are the initial estimates of user position and GPS time respectively and λc is the distance between repetitive signalling events, which is approximately 300 km for GPS C/A code epochs.
The updates to the initial estimates of receiver location and absolute time may once again be computed by means of equation (6). In this version of the algorithm, the vector ∇r can be formed by first constructing a vector Δt. The vector Δt, in units of milliseconds appropriate for C/A code GPS signals, can be constructed as follows:Δti=1000×[({tilde over (τ)}i−{circumflex over (D)}i/c)−({tilde over (τ)}0−{circumflex over (D)}0/c)]  (11)
Assuming GPS satellites, and the signalling events identified by the receiver will be the start of a 1 ms C/A code, {tilde over (τ)}i are the measured, sub-ms portions of the times-of-arrival after correction for the satellite clock bias or biases. The integer part of equation (11) may be removed by performing a modulo 1 ms operation and the result converted into meters.
                                          Δ            ⁢                                                  ⁢                          t              j                                =                                                    mod                ⁡                                  (                                                            Δ                      ⁢                                                                                          ⁢                                              t                        i                                                              ,                    1                                    )                                            ⁢                                                          ⁢                              if                ⁢                                                                  (                                                      Δ                    ⁢                                                                                  ⁢                                          t                      i                                                        >                  0.5                                )                            ⁢                              :                            ⁢                                                          ⁢              Δ              ⁢                                                          ⁢                              t                i                                      =                                          Δ                ⁢                                                                  ⁢                                  t                  i                                            -              1                                      ⁢                                  ⁢                              Δ            ⁢                                                  ⁢                          r              i                                =                                    c              1000                        ⁢            Δ            ⁢                                                  ⁢                          t              i                                                          (        12        )            
Once vector Δri has been constructed equation (6) can be solved to compute the position and time updates.
For both algorithms described above, equation (6) may be straightforwardly solved using standard techniques—for example, equation (13) is used to solve for over-determined least squares systems with uniform weighting:ΔX=(∇HT·∇H)−1·∇HT·∇r  (13)
Designating one of the satellites as the reference satellite may provide two advantages in the algorithms described above: first, it addresses the issue of integer ambiguity in the measured times-of-arrival; and second, it removes the receiver clock bias as an unknown at the instant of measurement, as the arrival of each signalling event is measured with reference to the arrival of the signalling event from the reference satellite. In this way, the receiver clock bias does not contaminate the measurements and does not enter into the location calculations. The receiver clock is used, however, to provide a timescale for measuring the time differences between the arrival times of the various signalling events; for example, using the intervals between the ‘ticks’ of the receiver clock to measure time differences.
Unknown Position
Each of the approaches to obtaining a location-fix in the absence of absolute-time described above requires estimates of both absolute time and receiver position to ‘seed’ the algorithm. If those estimates are sufficiently close to the actual values for absolute time and receiver position then the algorithms will converge on the actual values after a few iterations. If, however, the initial estimates are too far from the actual values, the algorithm will fail. In most scenarios absolute time will be reasonably well-known, either because the receiving device's own clock is sufficiently accurate or because another reasonably accurate time-source is readily available. If extended ephemeris is available, then knowledge of absolute time enables the position of the satellites to be evaluated, but unless full (i.e. unambiguous) pseudo-ranges are available, it is not possible to locate the receiver.
For these approaches to converge on the correct receiver position, the estimated position has typically to be accurate to the order of 50 to 100 km. Often this is achieved by obtaining an initial position from a server. However, there are many situations in which receiver position will be completely unknown. For example, when a user has just got off a aeroplane in a new location, the estimated receiver position could be thousands of miles in error. It would be advantageous to do away with the need for an initial position and require only an approximate time; in other words, to avoid contacting a server while still retaining the ability to get a rapid fix.
U.S. Pat. No. 6,417,801 describes a method in which, if the position of the receiver is completely unknown, the space of all possible a-priori positions is divided into a 100 km by 100 km latitude-longitude grid. Altitude is assigned from a look-up table of topographical altitudes. The process is then iterated across all possible a-priori positions. In effect, this amounts to iterating over the surface of the globe testing each location hypothesis in turn until the correct one is found, through a sequence of unaided elimination. This is an inefficient procedure which does not take into account knowledge which is available to the user's GNSS receiver. As a result, the prior art algorithms require considerable computation effort, too much for practical implementation and using energy, often from a battery source.
There is therefore a need for an improved mechanism for determining the location of a receiver when position is unknown.